package com.jiang.daily.Q1847;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.TreeSet;

/**
 * @author Jiang
 * @version 1.0
 * @date 2024/12/16 21:17
 */
public class Solution {
    // 离线算法(先将全部收集完数据后，再进行一次性的处理)
    public int[] closestRoom(int[][] rooms, int[][] queries) {
        int r_len = rooms.length;
        int q_len = queries.length;

        // 创建事件列表，将房间事件和询问事件放入列表（收集全部数据）
        ArrayList<Event> events = new ArrayList<>();
        for (int i = 0; i < r_len; i++) {
            // 房间事件
            events.add(new Event(0, rooms[i][1], rooms[i][0], i));
        }
        for (int i = 0; i < q_len; i++) {
            // 询问事件
            events.add(new Event(1, queries[i][1], queries[i][0], i));
        }
        // 对事件列表进行排序
        Collections.sort(events);
        // 创建结果数组
        int[] res = new int[q_len];
        Arrays.fill(res, -1);
        // 使用TreeSet存储房间id，保证有序
        TreeSet<Integer> set = new TreeSet<>();
        // 遍历事件（一次性处理）
        for (Event event : events) {
            // 如果是房间事件，则将房间id放入TreeSet中
            if (event.type == 0) {
                set.add(event.id);
            } else {
                // 如果是查询事件，则从TreeSet中找到最接近的房间id
                // 使用ceiling方法找到大于等于当前查询事件id的最小房间id
                Integer higher = set.ceiling(event.id);
                // 使用floor方法找到小于等于当前查询事件id的最大房间id
                Integer lower = set.floor(event.id);
                // 查询事件id和房间id的最小差值
                int dist = Integer.MAX_VALUE;
                // higher为空，则说明没有大于等于当前查询事件id的房间id。 如果higher不为空且最小房间id - 查询事件id 小于 dist
                if (higher != null && higher - event.id < dist) {
                    dist = higher - event.id;
                    // 将结果数组中对应索引的值设置为higher
                    res[event.origin] = higher;
                }
                // lower为空，则说明没有小于等于当前查询事件id的房间id。 如果lower不为空且查询事件id - 最小房间id 小于等于 dist（等于是因为题目要求如果dist一样，选房间id小的）
                if (lower != null && event.id - lower <= dist) {
                    // 将结果数组中对应索引的值设置为lower
                    res[event.origin] = lower;
                }

            }
        }
        return res;
    }
    // 暴力解法
    // public int[] closestRoom(int[][] rooms, int[][] queries) {
    //     int r_len = rooms.length;
    //     int q_len = queries.length;
    //     ArrayList<Integer> list = new ArrayList<>();
    //     // 根据房间面积降序排序
    //     Arrays.sort(rooms, (o1, o2) -> o2[1] - o1[1]);
    //     for (int i = 0; i < q_len; i++) {
    //         int roomsId = -1; // 满足查询的房间id
    //         int dist = Integer.MAX_VALUE; // 绝对值最小的差值
    //         for (int j = 0; j < r_len; j++) {
    //             // 如果当前房间面积小于minSize
    //             if (queries[i][1] > rooms[j][1])
    //                 break;
    //             int t = Math.abs(queries[i][0] - rooms[j][0]); // 绝对值差值
    //             // 如果绝对值差值小于differ，则替换满足查询房间的id
    //             if (t < dist) {
    //                 dist = t;
    //                 roomsId = rooms[j][0];
    //             } else if (t == dist && rooms[j][0] < roomsId) { // 如果等于，且当前id小于roomsId，则替换
    //                 roomsId = rooms[j][0];
    //             }
    //         }
    //         list.add(roomsId);
    //     }
    //     return list.stream().mapToInt(Integer::intValue).toArray();
    // }
}

class Event implements Comparable<Event> {
    // 事件类型，房间面积， 房间id， 结果数组中的索引
    int type, size, id, origin;

    public Event(int type, int size, int id, int origin) {
        this.type = type;
        this.size = size;
        this.id = id;
        this.origin = origin;
    }

    @Override
    public int compareTo(Event that) {
        // 根据size降序排序，如果size相同，则根据type降序排序，保证房间面积相等时，询问事件在房间事件后面
        if (this.size != that.size) {
            return Integer.compare(that.size, this.size);
        } else {
            return Integer.compare(this.type, that.type);
        }
    }
}